%%%-------------------------------------------------------------------
%%% File    : p50.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% The prime 41, can be written as the sum of six consecutive primes:
%%% 41 = 2 + 3 + 5 + 7 + 11 + 13
%%%
%%% This is the longest sum of consecutive primes that adds to a prime 
%%% below one-hundred.
%%%
%%% The longest sum of consecutive primes below one-thousand that adds 
%%% to a prime, contains 21 terms, and is equal to 953.
%%%
%%% Which prime, below one-million, can be written as the sum of the 
%%% most consecutive primes?
%%%
%%% Created :  4 Jan 2009
%%%-------------------------------------------------------------------
-module(p50).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function:  solution(N) -> {Count, Number}
%% Description: Find the prime equal to the sum of a sequence of consecutive primes with the longest
%% sequence length which is bellow N. Returns a tuple of the length of the sequence and the number itself.
%%--------------------------------------------------------------------
solution(N) ->
    {PrimesTbl, Primes} = primes(N),
    for(PrimesTbl, N, 0, 0, Primes).
    
%%====================================================================
%% Internal functions
%%====================================================================
% For every prime calculate the maximum "chain sum" it starts that is
% prime and less than Max.
% Only check chains longer than the current maximum and stop once
% the length of a chain whose sum exeeds Max is shorter than the current
% maximum length. The primes 
for(_PrimesTbl, _Max, MaxL, MaxN, []) -> {MaxL, MaxN};
for(PrimesTbl, Max, MaxL, MaxN, [H|T]) ->
    {L, N, TestedL} = prime_sum(PrimesTbl, Max, MaxL, T, 1, H, 1, H),
    case true of
        true when L > MaxL->
            for(PrimesTbl, Max, L, N, T);
        _ when TestedL < MaxL -> {MaxL, MaxN}; %break, no point searching more
        _ -> for(PrimesTbl, Max, MaxL, MaxN, T)
    end.

%Find the longest sequence of consecutive primes suming to a prime and starting with a given number
prime_sum(_PrimesTbl, _Max, _MaxL, [], BestL, Best, AccL, _) -> {BestL, Best, AccL};
prime_sum(_, Max, _, _, BestL, Best, AccL, Acc)  when Acc >= Max -> {BestL, Best, AccL};
prime_sum(PrimesTbl, Max, MaxL, [H|T], BestL, Best, AccL, Acc) ->
    case AccL > MaxL andalso ets:member(PrimesTbl, Acc) of
        true -> prime_sum(PrimesTbl, Max, MaxL, T, AccL, Acc, AccL + 1, Acc + H);
        _ -> prime_sum(PrimesTbl, Max, MaxL, T, BestL, Best, AccL + 1, Acc + H)
    end.

%Return a list of all primes bellow Max and a ets table with them as keys (used for further fast checks)
primes(Max) ->
    Tbl = ets:new(primes, []),
    ets:insert(Tbl, {2}),
    primes(3, Max, Tbl, [2]).

primes(I, Max, Tbl, Primes) when I > Max-> {Tbl, Primes};
primes(I, Max, Tbl, Primes) ->
    case is_prime(I, math:sqrt(I), Primes) of
        true ->
            ets:insert(Tbl, {I}),
            primes(I + 2, Max, Tbl, lists:append(Primes, [I]));
        _ -> primes(I + 2, Max, Tbl, Primes)
    end.

%check if a number is prime using a list of all previous primes
is_prime(_, Sqrt, [H|_]) when H > Sqrt -> true; 
is_prime(N, _, [H|_]) when N rem H =:= 0 -> false; 
is_prime(N, Sqrt, [_|T]) -> is_prime(N, Sqrt, T).
